/*
 * @Author: szx
 * @Date: 2022-03-20 11:48:37
 * @LastEditTime: 2022-03-20 14:16:17
 * @Description:
 * @FilePath: \leetcode\6000-6100\6029\6029.js
 */
/**
 * @param {number} numArrows
 * @param {number[]} aliceArrows
 * @return {number[]}
 */
var maximumBobPoints = function (numArrows, aliceArrows) {
    // dp[i][j]表示前i个靶子，使用j支箭的最优解
    const dp = new Array(13).fill(0).map(() => new Array(numArrows + 1).fill(0));
    for (let i = 1; i <= 12; i++) {
        for (j = 1; j <= numArrows; j++) {
            const num = aliceArrows[i] + 1;
            if (j - num >= 0) {
                dp[i][j] = Math.max(dp[i - 1][j - num] + i, dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[12][numArrows];
};

var maximumBobPoints = function (numArrows, aliceArrows) {
    // dp[i][j]表示前i个靶子，使用j支箭的最优解
    const dp = new Array(13).fill(0).map(() => new Array(numArrows + 1).fill(0));
    const res = new Array(12).fill(0);
    for (let i = 1; i <= 12; i++) {
        for (let j = numArrows; j >= 1; j--) {
            const num = aliceArrows[i] + 1;
            if (j - num >= 0) {
                dp[i][j] = Math.max(dp[i - 1][j - num] + i, dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    let j = numArrows;
    for (let i = 12; i >= 1; i--) {
        // console.log(dp[i][numArrows]);
        if (dp[i][j] == dp[i - 1][j]) continue;
        if (dp[i][j] == dp[i - 1][j - aliceArrows[i] - 1] + i) {
            res[i] = aliceArrows[i] + 1;
            j -= aliceArrows[i] + 1;
        }
    }
    res[0] += j;
    return res;
};

/**
 * @param {number} numArrows
 * @param {number[]} aliceArrows
 * @return {number[]}
 */
var maximumBobPoints = function (numArrows, aliceArrows) {
    let res;
    let max = 0;
    const dfs = (path, index, left, score, alicescore) => {
        if (score >= alicescore) {
            if (score > max) {
                max = score;
                path[0] += left;
                res = Array.from(path);
                path[0] -= left;
            }
        }
        for (let i = index; i < 12; i++) {
            if (left < aliceArrows[i] + 1) continue;
            path[i] = aliceArrows[i] + 1;
            dfs(path, i + 1, left - aliceArrows[i] - 1, score + i, alicescore - i);
            path[i] = 0;
        }
    };
    const path = new Array(12).fill(0);
    const alicescore = aliceArrows.reduce((prev, curv, index) => prev + (curv > 0 ? index : 0), 0);
    dfs(path, 0, numArrows, 0, alicescore);
    return res;
};
console.log(maximumBobPoints(9, [1, 1, 0, 1, 0, 0, 2, 1, 0, 1, 2, 0]));
// console.log(maximumBobPoints(3, [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2]));

// const alice = [1, 1, 0, 1, 0, 0, 2, 1, 0, 1, 2, 0];
// const bob = [0, 0, 0, 0, 1, 1, 0, 0, 1, 2, 3, 1];
// // const bob = [0, 0, 0, 2, 3, 2, 0, 0, 1, 0, 0, 1];
// console.log(
//     bob.reduce((a, b) => a + b),
//     0
// );
// let res = 0;
// for (let i = 0; i < 12; i++) {
//     if (alice[i] < bob[i]) {
//         res += i;
//     }
// }
// console.log(res);
